// 给定一个整数n，计算第n个斐波那契数

// 递归公式 f(n) = f(n-1) + f(n-2)
// 明确终止条件  f(0) = 0, f(1) = 1
// 翻译为递归代码
// 时间复杂度 On
// 空间复杂度 On

function fib(n) {
    if (n === 0) {
        return 0
    }
    if (n === 1) {
        return 1
    }
    return fib(n - 1) + fib(n - 2)
}

console.log(fib(15));

// 优化
// 时间复杂度 On
// 空间复杂度 On
function fib2(n, first = 0, second = 1) {
    if (n <= 0) {
        return 0
    }
    if (n === 1) {
        return 1
    }
    if (n < 3) {
        return first + second
    } else {
        return fib2(n - 1, second, first + second)
    }
}

console.log(fib2(15));